class Solution
{
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
public:
    void solveSudoku(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = true;
                    grid[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    for (int val = 1; val <= 9; val++)
                    {
                        if (!row[i][val] && !col[j][val] && !grid[i / 3][j / 3][val])
                        {
                            board[i][j] = val + '0';
                            row[i][val] = col[j][val] = grid[i / 3][j / 3][val] = true;
                            if (dfs(board)) return true;
                            board[i][j] = '.';
                            row[i][val] = col[j][val] = grid[i / 3][j / 3][val] = false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};
class Solution
{
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
public:
    bool isValidSudoku(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) return false;
                    row[i][num] = true;
                    col[j][num] = true;
                    grid[i / 3][j / 3][num] = true;
                }
            }
        }
        return true;
    }
};
class Solution
{
    vector<string> path;
    vector<vector<string>> ret;
    vector<bool> col;
    vector<bool> dig1;
    vector<bool> dig2;
    int n;
public:
    vector<vector<string>> solveNQueens(int _n)
    {
        n = _n;
        col = vector<bool>(n);
        dig1 = dig2 = vector<bool>(2 * n);
        path = vector<string>(n, string(n, '.'));
        dfs(0);
        return ret;
    }
    void dfs(int r)
    {
        if (r == n)
        {
            ret.push_back(path);
            return;
        }
        for (int j = 0; j < n; j++)
        {
            if (!col[j] && !dig1[j - r + n] && !dig2[j + r])
            {
                path[r][j] = 'Q';
                col[j] = true;
                dig1[j - r + n] = dig2[j + r] = true;
                dfs(r + 1);
                path[r][j] = '.';
                col[j] = false;
                dig1[j - r + n] = dig2[j + r] = false;
            }
        }
    }
};
class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
    int sum = 0;
    int target;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
    {
        target = _target;
        dfs(candidates, 0);
        return ret;
    }
    void dfs(vector<int>& candidates, int pos)
    {
        if (sum > target) return;
        if (sum == target)
        {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i < candixdates.size(); i++)
        {
            sum += candidates[i];
            path.push_back(candidates[i]);
            dfs(candidates, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
};
class Solution
{
    int path = 0;
    int ret = 0;
    int target;
public:
    int findTargetSumWays(vector<int>& nums, int _target)
    {
        target = _target;
        dfs(nums, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos)
    {
        if (pos == nums.size())
        {
            if (path == target) ret++;
            return;
        }
        path += nums[pos];
        dfs(nums, pos + 1);
        path -= nums[pos];

        path -= nums[pos];
        dfs(nums, pos + 1);
        path += nums[pos];
    }
};
class Solution
{
    vector<int> path;
    vector<vector<int>> ret;
    int n, k;
public:
    vector<vector<int>> combine(int _n, int _k)
    {
        n = _n;
        k = _k;
        dfs(1);
        return ret;
    }
    void dfs(int pos)
    {
        if (path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i <= n; i++)
        {
            path.push_back(i);
            dfs(i + 1);
            path.pop_back();
        }
    }
};